public class AVLTree<T extends Comparable<T>> {

    private AVLNode<T> mRoot;

    private  class AVLNode<T extends Comparable<T>> {
        T key;
        AVLNode<T> left;
        AVLNode<T> right;
        int height;

        AVLNode(T key){
            this(key,null,null);
        }

        AVLNode (T key,AVLNode<T> lt,AVLNode<T> rt){
            this.key = key;
            this.left = lt;
            this.right = rt;
            height = 0;
        }
    }

    public AVLTree(){
        mRoot = null;
    }

    private int height(AVLNode<T> t){
        return t==null?0:t.height;
    }

    public int height(){
        return height(mRoot);
    }

    private int max(int a,int b){
        return a>b?a:b;
    }

    private void preOrder(AVLNode<T> tree){
        if(tree!=null){
            System.out.println(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder(){
        preOrder(mRoot);
    }


    private void inOrder(AVLNode<T> tree){
        if(tree!=null){
            inOrder(tree.left);
            System.out.println(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder(){
        inOrder(mRoot);
    }


    private void postOrder(AVLNode<T> tree){
        if(tree!=null){
            postOrder(tree);
            postOrder(tree);
            System.out.println(tree.key+"");
        }
    }

    public void postOrder(){
        postOrder(mRoot);
    }

    private AVLNode<T> search(AVLNode x,T key){
        if(x==null){
            return x;
        }
        int cmp = key.compareTo((T) x.key);
        if(cmp<0){
            return search(x.left,key);
        }else if(cmp>0){
            return search(x.right,key);
        }else{
            return x;
        }
    }


    public AVLNode<T> search(T key){
        return search(mRoot,key);
    }

    private AVLNode<T> minimum(AVLNode<T> tree){
        if(tree==null)
            return null;
        while(tree.left!=null){
            tree = tree.left;
        }
        return tree;
    }


    public T minimum(){
        AVLNode<T> p = minimum(mRoot);
        if(p!=null)
            return p.key;
        return null;
    }

    private AVLNode<T> maximum(AVLNode<T> tree){
        while(tree!=null){
            tree = tree.right;
        }
        return tree;
    }

    public T maximum(){
        AVLNode<T> p = maximum(mRoot);
        if(p!=null)
            return p.key;
        return null;
    }



    private AVLNode<T> leftLeftRotate(AVLNode<T> y){
        AVLNode<T> x = y.left;
        AVLNode<T> t2 = x.right;
        x.right = y;
        y.left = t2;
        y.height = max(y.left.height,y.right.height)+1;
        x.height = max(x.left.height,x.right.height)+1;
        return y;
    }

    private AVLNode<T> rightRightRotation(AVLNode<T> k1){
        AVLNode<T> k2;

        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max(height(k1.left),height(k2.right))+1;
        k2.height = max(height(k2.left),height(k2.right))+1;
        return k2;
    }

    /**
     * 左右
     * */
    private AVLNode<T> leftRightRotation(AVLNode<T> k3){
        k3.left = rightRightRotation(k3.left);
        return leftLeftRotate(k3);
    }

    private AVLNode<T> rightLeftRotation(AVLNode<T> k1){
        k1.right = leftLeftRotate(k1.right);
        return rightRightRotation(k1);
    }


//    private AVLNode<T> successor(AVLNode<T> x){
//        if(x.right!=null){
//            return minimum(x.right);
//        }
//
//        AVLNode<T> y = x.parent;
//    }

    private AVLNode<T> insert(AVLNode<T> tree,T key){
        if(tree==null){
            tree = new AVLNode<T>(key,null,null);
        }else{
            int cmp = key.compareTo(tree.key);
            if(cmp<0){ //应该将key插入到tree的左子树
                tree.left = insert(tree.left,key);
                //插入节点以后，如果AVL树失去平衡，则进行相应的调整
                if(height(tree.left)-height(tree.right) == 2){
                    if(key.compareTo(tree.left.key)<0){
                        tree = leftLeftRotate(tree);
                    }else{
                        tree = leftRightRotation(tree);
                    }
                }
            }else if(cmp>0){
                tree.right = insert(tree.right,key);
                if(height(tree.right)-height(tree.left) == 2){
                    if(key.compareTo(tree.right.key)>0){
                        tree = rightRightRotation(tree);
                    }else{
                        tree = rightLeftRotation(tree);
                    }
                }

            }else{
                System.out.println("添加失败，不允许添加相同节点");
            }


        }
        tree.height = max( height(tree.left), height(tree.right)) + 1;
        return tree;
    }

    public void insert(T key){
        mRoot = insert(mRoot,key);
    }

    private AVLNode<T> remove(AVLNode<T> tree,AVLNode<T> z){
        //根节点为空，或者要删除的节点为空，直接返回Null
        if(tree==null||z==null){
            return null;
        }

        int cmp = z.key.compareTo(tree.key);
        if(cmp<0){
            tree.left = remove(tree.left,z);
            if(height(tree.right)-height(tree.left) == 2){
                AVLNode<T> r = tree.right;
                if(height(r.right)>height(r.left)){
                    tree = rightRightRotation(tree);
                }else{
                    tree = rightLeftRotation(tree);
                }
            }
        }else if(cmp>0){
            tree.right = remove(tree.right,z);
            if(height(tree.left)-height(tree.right)==2){
                AVLNode<T> l = tree.left;
                if(height(l.left)>height(l.right)){
                    tree = leftLeftRotate(tree);
                }else{
                    tree = leftRightRotation(tree);
                }
            }
        }else{
            //tree是对应要删除的节点
            //tree的左右孩子都非空
            if((tree.left!=null)&&(tree.right!=null)){
                if(height(tree.left)>height(tree.right)){
                    //如果tree的左子树比右子树高
                    AVLNode<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left,max);
                }else{
                    AVLNode<T> min = maximum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right,min);
                }
            }else{
                AVLNode<T> tmp = tree;
                tree = (tree.left!=null) ? tree.left : tree.right;
                tmp = null;
            }
        }

        return null;
    }

    public void remove(T key) {
        AVLNode<T> z;

        if ((z = search(mRoot, key)) != null)
            mRoot = remove(mRoot, z);
    }

}

